package com.leetcode.题库;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-02-19 18:02
 */
public class 题库_0969_煎饼排序 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] arr = {3,2,4,1};
    List<Integer> result = solution.pancakeSort(arr);
    System.out.println(result);
    System.out.println(Arrays.toString(arr));
  }

  static
  class Solution {
    public List<Integer> pancakeSort(int[] arr) {

      if (arr.length < 2) {
        return new ArrayList<>();
      }

      List<Integer> result = new ArrayList<>();

      for (int end = arr.length - 1; end > 0; --end) {
        int maxIndex = 0;
        for (int i = 1; i <= end; ++i) {
          maxIndex = arr[i] >= arr[maxIndex] ? i : maxIndex;
        }
        if (maxIndex == end) {
          continue;
        }

        // 先把最大值放到第一位
        result.add(maxIndex + 1);
        reverse(arr, maxIndex);

        // 再把最大值放到最后一位
        result.add(end + 1);
        reverse(arr, end);

      }

      return result;
    }

    private void reverse(int[] arr, int k) {
      int s = 0;
      while (s < k) {
        int tmp = arr[k];
        arr[k] = arr[s];
        arr[s] = tmp;
        ++s;
        --k;
      }
    }
  }

}
